/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lily
 * Date: 2024-09-25
 * Time: 10:54
 */
public class test_1 {
    public static boolean exist(char[][] board, String word) {
        int n = 0;
        return (for_exist(board, word, 0, 0, 0));
    }

    public static boolean for_exist(char[][] board, String word, int x, int y, int n) {
        if (n == word.length()) {
            return true;
        }
        if (x>=board.length){
            return false;
        }
        if (y>=board[0].length-1){
            return false;
        }
        for (int i =  x; i < board.length; i++) {
            for (int j = y; j < board[0].length; j++) {
                if (board[i][j]==word.charAt(n)){
                    return (for_exist(board, word, i, j+1, n+1))||(for_exist(board, word, i+1, j, n+1));

                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        char[][] arr={{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word="ABCCED";
        System.out.println(exist(arr, word));

    }
}
